package com.kaizen.leet148;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 这里可以先做21. 合并两个有序链表
 *
 * 148. 排序链表
 * 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
 *
 * 示例 1:
 * 输入: 4->2->1->3
 * 输出: 1->2->3->4
 *
 * @author kaizen
 * @date 2020/4/30 20:30
 */
public class SolutionKaizen {

    public ListNode sortList(ListNode head) {
        //递归终止条件
        if(head==null||head.next==null) {
            return head;
        }
        //快慢指针找到中点
        ListNode fast=head.next;
        ListNode low=head;
        while(fast!=null&&fast.next!=null) {
            fast=fast.next.next;
            low=low.next;
        }
        //找到中点,截断链表
        ListNode temp=low.next;
        low.next=null;
        ListNode left=sortList(head);
        ListNode right=sortList(temp);
        ListNode h=new ListNode(0);
        ListNode cur=new ListNode(0);
        h.next=cur;
        //合并链表
        while(left!=null&&right!=null) {
            if(left.val<=right.val) {
                cur.next=left;
                cur=cur.next;
                left=left.next;
            }else {
                cur.next=right;
                cur=cur.next;
                right=right.next;
            }
        }
        if(left!=null) {
            cur.next=left;
        }
        if(right!=null) {
            cur.next=right;
        }
        return h.next.next;
    }

    /**
     * 根据步长分隔链表
     * @param head
     * @param step
     * @return
     */
    private ListNode split(ListNode head, int step) {
        if (head == null) return null;

        for (int i = 1; head.next != null && i < step; i++) {
            head = head.next;
        }

        ListNode right = head.next;
        head.next = null;
        return right;
    }

    /**
     * 获取链表的长度
     * @param head
     * @return
     */
    private int listNodeLength(ListNode head) {
        int length = 0;
        ListNode curr = head;

        while (curr != null) {
            length++;
            curr = curr.next;
        }

        return length;
    }

    /**
     *   合并两个有序链表
     */
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode sentry = new ListNode(-1);
        ListNode curr = sentry;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }

            curr = curr.next;
        }

        curr.next = l1 != null ? l1 : l2;
        return sentry.next;
    }

    /**
     * 这里还是采用堆来排序
     * 时间复杂度 O(n log n)
     * 空间复杂度O(n)
     */
    public ListNode sortList1(ListNode head) {
        if (head == null) {
            return null;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return b - a;
            }
        });
        ListNode node = head;
        while (node != null) {
            priorityQueue.add(node.val);
            node = node.next;
        }
        ListNode res = new ListNode(priorityQueue.poll());
        while (!priorityQueue.isEmpty()) {
            ListNode node1 = new ListNode(priorityQueue.poll());
            node1.next = res;
            res = node1;
        }
        return res;
    }

   
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

}
